#include <iostream>
#include <vector>
using namespace std;

template <typename T, int M>
class BTreeNode {
    bool isLeaf;
    vector<T> keys;
    vector<BTreeNode*> children;
    int numKeys;

public:
    BTreeNode(bool leaf = true) : isLeaf(leaf), numKeys(0) {
        keys.resize(M-1);
        children.resize(M, nullptr);
    }

    ~BTreeNode() {
        for(auto child : children) {
            if(child) delete child;
        }
    }

    bool search(T key) {
        int i = 0;
        while(i < numKeys && key > keys[i]) i++;
        if(i < numKeys && keys[i] == key) return true;
        if(isLeaf) return false;
        return children[i]->search(key);
    }

    void insert(T key) {
        int i = numKeys-1;

        if(isLeaf) {
            while(i >= 0 && keys[i] > key) {
                keys[i+1] = keys[i];
                i--;
            }
            keys[i+1] = key;
            numKeys++;
        } else {
            while(i >= 0 && keys[i] > key) i--;
            if(children[i+1]->numKeys == M-1) {
                splitChild(i+1, children[i+1]);
                if(keys[i+1] < key) i++;
            }
            children[i+1]->insert(key);
        }
    }

    void splitChild(int i, BTreeNode* y) {
        BTreeNode* z = new BTreeNode(y->isLeaf);
        z->numKeys = M/2 - 1;

        for(int j = 0; j < M/2-1; j++)
            z->keys[j] = y->keys[j+M/2];

        if(!y->isLeaf) {
            for(int j = 0; j < M/2; j++)
                z->children[j] = y->children[j+M/2];
        }

        y->numKeys = M/2 - 1;

        for(int j = numKeys; j >= i+1; j--)
            children[j+1] = children[j];

        children[i+1] = z;

        for(int j = numKeys-1; j >= i; j--)
            keys[j+1] = keys[j];

        keys[i] = y->keys[M/2-1];
        numKeys++;
    }

    void remove(T key) {
        int idx = findKey(key);

        if(idx < numKeys && keys[idx] == key) {
            if(isLeaf) {
                for(int i = idx+1; i < numKeys; i++)
                    keys[i-1] = keys[i];
                numKeys--;
            } else {
                removeFromNonLeaf(idx);
            }
        } else {
            if(isLeaf) return;

            bool flag = (idx == numKeys);

            if(children[idx]->numKeys < M/2)
                fill(idx);

            if(flag && idx > numKeys)
                children[idx-1]->remove(key);
            else
                children[idx]->remove(key);
        }
    }

private:
    int findKey(T key) {
        int idx = 0;
        while(idx < numKeys && keys[idx] < key) idx++;
        return idx;
    }

    void removeFromNonLeaf(int idx) {
        T key = keys[idx];

        if(children[idx]->numKeys >= M/2) {
            T pred = getPred(idx);
            keys[idx] = pred;
            children[idx]->remove(pred);
        } else if(children[idx+1]->numKeys >= M/2) {
            T succ = getSucc(idx);
            keys[idx] = succ;
            children[idx+1]->remove(succ);
        } else {
            merge(idx);
            children[idx]->remove(key);
        }
    }

    T getPred(int idx) {
        BTreeNode* cur = children[idx];
        while(!cur->isLeaf) cur = cur->children[cur->numKeys];
        return cur->keys[cur->numKeys-1];
    }

    T getSucc(int idx) {
        BTreeNode* cur = children[idx+1];
        while(!cur->isLeaf) cur = cur->children[0];
        return cur->keys[0];
    }

    void fill(int idx) {
        if(idx != 0 && children[idx-1]->numKeys >= M/2)
            borrowFromPrev(idx);
        else if(idx != numKeys && children[idx+1]->numKeys >= M/2)
            borrowFromNext(idx);
        else
            idx != numKeys ? merge(idx) : merge(idx-1);
    }

    void borrowFromPrev(int idx) {
        BTreeNode* child = children[idx];
        BTreeNode* sibling = children[idx-1];

        for(int i = child->numKeys-1; i >= 0; i--)
            child->keys[i+1] = child->keys[i];

        if(!child->isLeaf) {
            for(int i = child->numKeys; i >= 0; i--)
                child->children[i+1] = child->children[i];
        }

        child->keys[0] = keys[idx-1];

        if(!child->isLeaf)
            child->children[0] = sibling->children[sibling->numKeys];

        keys[idx-1] = sibling->keys[sibling->numKeys-1];

        child->numKeys++;
        sibling->numKeys--;
    }

    void borrowFromNext(int idx) {
        BTreeNode* child = children[idx];
        BTreeNode* sibling = children[idx+1];

        child->keys[child->numKeys] = keys[idx];

        if(!child->isLeaf)
            child->children[child->numKeys+1] = sibling->children[0];

        keys[idx] = sibling->keys[0];

        for(int i = 1; i < sibling->numKeys; i++)
            sibling->keys[i-1] = sibling->keys[i];

        if(!sibling->isLeaf) {
            for(int i = 1; i <= sibling->numKeys; i++)
                sibling->children[i-1] = sibling->children[i];
        }

        child->numKeys++;
        sibling->numKeys--;
    }

    void merge(int idx) {
        BTreeNode* child = children[idx];
        BTreeNode* sibling = children[idx+1];

        child->keys[M/2-1] = keys[idx];

        for(int i = 0; i < sibling->numKeys; i++)
            child->keys[i+M/2] = sibling->keys[i];

        if(!child->isLeaf) {
            for(int i = 0; i <= sibling->numKeys; i++)
                child->children[i+M/2] = sibling->children[i];
        }

        for(int i = idx+1; i < numKeys; i++)
            keys[i-1] = keys[i];

        for(int i = idx+2; i <= numKeys; i++)
            children[i-1] = children[i];

        child->numKeys += sibling->numKeys+1;
        numKeys--;

        sibling->children.clear();
        delete sibling;
    }
};

template <typename T, int M>
class BTree {
    BTreeNode<T, M>* root;

public:
    BTree() : root(nullptr) {}

    ~BTree() {
        if(root) delete root;
    }

    bool search(T key) {
        return root ? root->search(key) : false;
    }

    void insert(T key) {
        if(!root) {
            root = new BTreeNode<T, M>(true);
            root->keys[0] = key;
            root->numKeys = 1;
        } else {
            if(root->numKeys == M-1) {
                BTreeNode<T, M>* newRoot = new BTreeNode<T, M>(false);
                newRoot->children[0] = root;
                newRoot->splitChild(0, root);

                int i = 0;
                if(newRoot->keys[0] < key) i++;
                newRoot->children[i]->insert(key);

                root = newRoot;
            } else {
                root->insert(key);
            }
        }
    }

    void remove(T key) {
        if(!root) return;

        root->remove(key);

        if(root->numKeys == 0) {
            BTreeNode<T, M>* tmp = root;
            if(root->isLeaf) {
                root = nullptr;
            } else {
                root = root->children[0];
            }
            tmp->children.clear();
            delete tmp;
        }
    }
};